package org.czl.leetCode1;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.PriorityQueue;

public class L743 {

    public static void main(String[] args) {
        System.out.println(networkDelayTime(new int[][]{{1, 2, 1}}, 2, 1));
    }
    public static int networkDelayTime(int[][] times, int n, int k) {
        List<List<int[]>> eg = new ArrayList();
        for(int i = 0 ; i <= n; i++){
            eg.add(new ArrayList());
        }
        for(int[] i : times){
            // x 到 y的点权值为z;
            int x = i[0];
            int y = i[1];
            int z = i[2];
            eg.get(x).add(new int[]{y, z});
        }
        //建图完成之后进行 djk最短路算法
        PriorityQueue<int[]> queue = new PriorityQueue<>((a, b) -> (a[1] - b[1]));
        queue.add(new int[]{k, 0});
        boolean[] set = new boolean[n + 1];
        int[] distance = new int[n + 1];
        Arrays.fill(distance, Integer.MAX_VALUE);
        distance[k] = 0;
        while(!queue.isEmpty()){
            //弹出的节点
            int[] ret = queue.poll();
            int u = ret[0];
            if(set[u]){
                continue;
            }
            set[u] = true;
            int dis = ret[1];
            for(int[] arr : eg.get(u)){
                int v = arr[0];//目的
                int coin = arr[1]; //权
                if(!set[v] && distance[u] + coin < distance[v]){
                    distance[v] = distance[u] + coin;
                    queue.add(new int[]{v, distance[u] + coin});
                }
            }
        }
        int ans = Integer.MIN_VALUE;
        for(int i = 1; i < distance.length; i++){
            if(distance[i] == Integer.MAX_VALUE)return -1;
            ans = Math.max(ans, distance[i]);
        }
        return ans;
    }
}
